package Auction;


import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

import _543cloud_new.Match;

public class Auction {

	static int INF = 1 << 20;

	int n;
	Graph_Auction singleGraph;
	int weight[][];
	int lx[], ly[]; // label
	boolean sx[], sy[];
	int[] match;
	int[] flag;
	Set<Match> matchset = new HashSet<Match>();

	public Auction() throws IOException {
		singleGraph = new Graph_Auction();
		double w[][] = singleGraph.weight;
		
		
		n = w.length;
		weight = new int[n][n];
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)
				weight[i][j] = (int)(w[i][j]*10);
		}
			
		match = new int[n];	//match array
		lx = new int[n];	//left label
		ly = new int[n];	//right label
		sx = new boolean[n];	//left visited
		sy = new boolean[n];	//right visted
		flag = new int[n];	//temp label
		init();
		
	}
	
	public void init() {
		for (int i=0; i<flag.length;flag[i++]=-1);
		for (int i=0;i<n;i++) {
			lx[i] = -INF;
			for (int j=0;j<n;j++) {
				lx[i] = Math.max(lx[i], weight[i][j]);
			}
		}
	}
	
	public void printresult(){
		boolean hasPerfactMatch = this.km();  
        if(hasPerfactMatch){
            System.out.println("The maximum match for this is :");
            int sumNum = 0;
            for(int i = 0;i < n;i++){
            	String ll = null, rr = null;
            	
//            	if(singleGraph.lnodes_name.keySet().contains(i))
            		ll = singleGraph.req.get(i).name;
//            	if(singleGraph.rnodes_name.keySet().contains(match[i]))
            		rr = singleGraph.help.get(match[i]).toString();   
            	
            	if(ll!=null && rr!=null ){
            		Match temp = new Match(ll,rr);
            		matchset.add(temp);
            	}
                sumNum += weight[i][match[i]];
            }
            double sum = sumNum/10.0;
            System.out.println(matchset);
            System.out.println("Maximum profit is ["+sum + "]");
        }
        else{
            System.out.println("No perfect Match");
        }
	}

	

	public boolean km() {
		int[][] map = new int[n][n];
		int dmin = INF;
		do {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (lx[i] + ly[j] == weight[i][j])
						map[i][j] = 1;
					else
						map[i][j] = 0;
				}
			}
			if (hasPerfectMatch(map))
				return true;
			

			//Adjust label and re-label
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (sx[i] && !sy[j]) {
						dmin = Math.min(dmin, lx[i]+ly[j]-weight[i][j]);
					}
				}
			}
			if (dmin != INF && dmin > 0) {
				for (int i=0;i<n;i++)
					if (sx[i])
						lx[i] -= dmin;
				for (int i=0;i<n;i++)
					if (sy[i])
						ly[i] += dmin;
			}
		} 
		while (dmin != INF && dmin>0);

		return false;

	}

	public boolean hasPerfectMatch(int[][] map) {
		int i, j;
		for (i=0;i<flag.length;i++)
			flag[i] = -1;
		for (i = 0; i < n; i++) {
			for (j=0; j<sx.length; sx[j++]=false);
			for (j=0; j<sy.length; sy[j++]=false);
			if (!path(i, map))
				break;
		}
		if (i < n)
			return false;
		return true;

	}

	public boolean path(int pos, int[][] map) {
		//DFS
		sx[pos] = true;
		for (int i = 0; i < n; i++) {
			if (map[pos][i] == 1 && !sy[i]) {
				sy[i] = true;
				if (flag[i] == -1 || path(flag[i],map)) {
					flag[i] = pos;
					for (int m=0; m<flag.length; m++)
						if (flag[m] >= 0)
							match[flag[m]] = m;
					return true;
				}
			}
		}
		return false;

	}


	public static void main(String[] args) throws IOException {
		Auction test = new Auction();
		test.printresult();
	}

}
